package 算法_100.简单;

/**
 * @Description 爬楼梯 （动态规划问题求解）
 * @Created by zhengqiang
 * @Date 2023/1/7 14:18
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 n=[1,45]
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class s4_爬楼梯 {
    public static void main(String[] args) {
        System.out.println("climbStairs1(4) = " + climbStairs1(4));
    }

    // 1.递归解法 长度为N,空间复杂度O(n) 时间复杂度（o(2^n）
    public static int climbStairs1(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs1(n - 1) + climbStairs1(n - 2);
    }

    // 2.递归解法 -去除已计算部分的解法 记忆化递归
    public static int climbStairs2(int n) {
        int memo[] = new int[n + 1];
        return climbMemo(n, memo);
    }

    public static int climbMemo(int n, int memo[]) {
        if (memo[n] > 0) return memo[n];
        if (n == 1) {
            return memo[n] = 1;
        } else if (n == 2) {
            return memo[n] = 2;
        } else {
            memo[n] = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
        }
        return memo[n];
    }


    // 动态规划解法 时间和空间复杂度均为O(n)
    public static int climbStairs(int n) {
        if (n == 1) return 1;
        int[] dp = new int[n + 1]; // 记录N个状态，从1到n依次更新
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
